package tree;

import org.junit.Test;
import java.util.*;
public class TreeDynamic {
    class Solution337 {
        //记忆性递归
        public int rob1(TreeNode root) {
            if (root == null) return 0;
            else return dfs(root);
        }
        Map<TreeNode, Integer> map = new HashMap<>();
        public int dfs(TreeNode root) {
            if (root == null) return 0;
            if (map.containsKey(root)) return map.get(root);
            int rob = root.val, not = 0;
            if (root.left != null) {
                rob += dfs(root.left.left) + dfs(root.left.right);
            }
            if (root.right != null) {
                rob += dfs(root.right.left) + dfs(root.right.right);
            }
            not = dfs(root.left) + dfs(root.right);
            int res = Math.max(rob, not);
            map.put(root, res);
            return res;
        }

        //这样的话，root与canRob的两个递归条件无法放入暂存池map中，因此只能暴力递归，导致超时
        public int dfs1(TreeNode root, boolean canRob) {
            if (root == null) return 0;
            int rob = 0, not = 0;
            if (canRob) {
                rob = root.val + dfs1(root.left, false) + dfs1(root.right, false);
            }
            not = dfs1(root.left, true) + dfs1(root.right, true);
            return Math.max(rob, not);
        }

        //树形动态规划，本质是一个填表【map】的过程
        Map<TreeNode, int[]> f = new HashMap<>();
        public int rob(TreeNode root) {
            if (root == null) return 0;
            fill(root);
            int[] res = f.get(root);
            return Math.max(res[0], res[1]);
        }

        public void fill(TreeNode root) {
            if (f.containsKey(root)) return; //防止多次计算null key
            if (root == null) {
                f.put(root, new int[]{0, 0});
                return;
            }
            //先来到最底层，自底向上填表
            fill(root.left);
            fill(root.right);
            int rob = root.val + f.get(root.left)[0] + f.get(root.right)[0]; //只能不偷下一层
            int[] nLeft = f.get(root.left), nRight = f.get(root.right);
            int not = Math.max(nLeft[0], nLeft[1]) + Math.max(nRight[0], nRight[1]);
            f.put(root, new int[]{not, rob});
        }

    }

    @Test
    public void test1() {
        Integer[] arr = {3,4,5,1,3,null,1};
        arr = new Integer[]{
            79,99,77,null,null,null,69,null,60,53,null,73,11,null,null,null,62,27,62,null,null,98,50,null,null,90,48,82,null,null,null,55,64,null,null,73,56,6,47,null,93,null,null,75,44,30,82,null,null,null,null,null,null,57,36,89,42,null,null,76,10,null,null,null,null,null,32,4,18,null,null,1,7,null,null,42,64,null,null,39,76,null,null,6,null,66,8,96,91,38,38,null,null,null,null,74,42,null,null,null,10,40,5,null,null,null,null,28,8,24,47,null,null,null,17,36,50,19,63,33,89,null,null,null,null,null,null,null,null,94,72,null,null,79,25,null,null,51,null,70,84,43,null,64,35,null,null,null,null,40,78,null,null,35,42,98,96,null,null,82,26,null,null,null,null,48,91,
            null,null,35,93,86,42,null,null,null,null,0,61,null,null,67,null,53,48,null,null,82,30,null,97,null,null,null,1,null,null};
        TreeNode root = TreeUtils.createTree(arr);
        Solution337 s = new Solution337();
        System.out.println(s.rob(root));
    }
}
